class Solution:
    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
        n_nums = len(binary)

        # dp[i] = [全是1,全是0,01都有以1结尾,01都有以0结尾]
        dp = [[0, 0, 0, 0] for _ in range(n_nums + 1)]
        for i in range(n_nums):
            if binary[i] == "0":
                dp[i + 1][0] = dp[i][0]
                dp[i + 1][1] = 1
                dp[i + 1][2] = dp[i][2]
                dp[i + 1][3] = dp[i][0] + dp[i][2]
            else:  # binary[i] == "1"
                dp[i + 1][0] = dp[i][0] + 1
                dp[i + 1][1] = dp[i][1]
                dp[i + 1][2] = dp[i][2] + dp[i][3]
                dp[i + 1][3] = dp[i][3]

        for row in dp:
            print(row)

        return sum(dp[-1])


if __name__ == "__main__":
    # print(Solution().numberOfUniqueGoodSubsequences(binary="001"))  # 2
    # print(Solution().numberOfUniqueGoodSubsequences(binary="11"))  # 2
    # print(Solution().numberOfUniqueGoodSubsequences(binary="101"))  # 5

    # 自制用例
    # print(Solution().numberOfUniqueGoodSubsequences(binary="111"))  # 3
    # print(Solution().numberOfUniqueGoodSubsequences(binary="110"))  # 5 (1 11 10 110 0)
    # print(Solution().numberOfUniqueGoodSubsequences(binary="101"))  # 5 (1 10 101 11 0)
    # print(Solution().numberOfUniqueGoodSubsequences(binary="011"))  # 3
    # print(Solution().numberOfUniqueGoodSubsequences(binary="100"))  # 4
    # print(Solution().numberOfUniqueGoodSubsequences(binary="010"))  # 3
    # print(Solution().numberOfUniqueGoodSubsequences(binary="001"))  # 2
    # print(Solution().numberOfUniqueGoodSubsequences(binary="000"))  # 1

    print(Solution().numberOfUniqueGoodSubsequences(binary="1111"))  # 4

    print(Solution().numberOfUniqueGoodSubsequences(binary="1110"))  # 7
    # 全是1 全是0 1结尾 0结尾
    # 1 0 0 0 (1)
    # 2 0 0 0 (1,11)
    # 3 0 0 0 (1,11,111)
    # 3 1 0 3 (1,11,111;0;10,110,1110)

    # print(Solution().numberOfUniqueGoodSubsequences(binary="1101"))  # 8

    print(Solution().numberOfUniqueGoodSubsequences(binary="10110"))  # 7
    # 1 0 0 0 (1)
    # 1 1 0 1 (1;0;10)
    # 2 1 1 1 (1,11;0;101;10)
    # 3 1 2 1 (1,11,111;0;101,1011;10)
    # 3 1 2 1 (1,11,111;0;101,1011;10)

    print(Solution().numberOfUniqueGoodSubsequences(binary="1010"))  # 7
    # 1 0 0 0 (1)
    # 1 1 0 1 (1;0;10)
    # 2 1 1 1 (1,11;0;101;10)
    # 2 1 1 3 (1,11;0;101;10,110,1010)

    print(Solution().numberOfUniqueGoodSubsequences(binary="1001"))  # 7
    # 1 0 0 0 (1)
    # 1 1 0 1 (1;0;10)
    # 1 1 0 2 (1;0;;10,100)
    # 2 1 2 2 (1;0;101,1001;10,100)

    # print(Solution().numberOfUniqueGoodSubsequences(binary="10101"))  # (1 11 111 0 0 10101 1010 101 10 100 1001)
